package chapter04_RecursionAndDynamic;

/**
 * 描述：
 *      最小编辑代价
 *      给定两个字符串str1 和str2，再给定三个整数ic、dc和rc，分别代表插入、删除和替
 * 换一个字符的代价，返回将str1 编辑成str2的最小代价.
 * @author hl
 * @date 2021/6/20 15:23
 */
public class MinCost {
    public static void main(String[] args) {
        MinCost minCost = new MinCost();
        String str1 = "abc";
        String str2 = "adc";
        int ic = 5;
        int dc = 3;
        int rc = 100;
        int cost = minCost.minCost1(str1, str2, ic, dc, rc);
        int cost2 = minCost.minCost2(str1, str2, ic, dc, rc);
        System.out.println(cost);
        System.out.println(cost2);
    }

    /**
     * 动态规划：
     * 构建一个二维数组dp，dp[i][j]表示将str1[0...i]的字符串编辑成str2[0...j]的字符串话费的最小代价
     *  以ic、de和re三个维度考虑，dp[i][j]的来自四个地方：
     *      1）将str1[0...i]编辑成str2[0...j-1]，然后增加一个字符，dp[i][j-1] + ic
     *      2）删除str1最后一个字符，将str1[0...i-1]编辑成str2[0...j]，dp[i-1][j] + dc
     *      3）如果str1[i]==str2[j]，那么dp[i][j] = dp[i-1][j-1]；否则dp[i][j] = dp[i-1][j-1] + rc
     */
    public int minCost1(String str1, String str2, int ic, int dc, int rc){
        if (str1 == null || str2 == null) {
            return 0;
        }
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dc * i;
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = ic * j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = dp[i - 1][j - 1] + rc;
                }
                dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
            }
        }
        return dp[m][n];
    }

    /**
     * 滚动数组进行空间优化，空间复杂度为O(min{m,n})
     */
    public int minCost2(String str1, String str2, int ic, int dc, int rc){
        if (str1 == null || str2 == null) {
            return 0;
        }
        int l = Math.max(str1.length(), str2.length());
        int s = Math.max(str1.length(), str2.length());
        if (str1.length() < str2.length()) {
            int temp = ic;
            ic = dc;
            dc = temp;
        }
        int[] dp = new int[s + 1];
        for (int j = 1; j < s; j++) {
            dp[j] = ic * j;
        }
        int pre = 0;
        int temp = 0;
        for (int i = 1; i <= l; i++) {
            pre = dp[0];
            dp[0] = dc * i;
            for (int j = 1; j <= s; j++) {
                temp = dp[j];
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[j] = pre;
                }else{
                    dp[j] = pre + rc;
                }
                dp[j] = Math.min(dp[j], temp + dc);
                dp[j] = Math.min(dp[j], dp[j - 1] + ic);
                pre = temp;
            }
        }
        return dp[s];
    }

}
